package io.github.hadyang.leetcode.offer;

import org.junit.Test;

/** @author haoyang.shi */
public class InversePairs {

  @Test
  public void test() {
    System.out.println(InversePairs(new int[] {3, 1, 2, 6, 8, 0}));
    System.out.println(InversePairs(new int[] {5, 7, 4, 6}));
    System.out.println(InversePairs(new int[] {1, 2, 3, 4, 5, 6, 7, 0}));
  }

  public int InversePairs(int[] array) {
    long[] sum = {0};
    if (array == null || array.length == 0) {
      return (int) sum[0];
    }

    int[] temp = new int[array.length];
    mergeSort(array, 0, array.length - 1, temp, sum);
    return (int) (sum[0] % 1000000007);
  }

  private void mergeSort(int[] array, int start, int end, int[] temp, long[] sum) {
    if (start == end) {
      return;
    }

    int mid = (start + end) / 2;

    mergeSort(array, start, mid, temp, sum);
    mergeSort(array, mid + 1, end, temp, sum);

    int f = mid, s = end;
    int t = end;
    while (f >= start && s >= mid + 1) {
      if (array[f] > array[s]) {
        temp[t--] = array[f--];
        sum[0] += s - mid;
      } else {
        temp[t--] = array[s--];
      }
    }

    while (f >= start) {
      temp[t--] = array[f--];
    }

    while (s >= mid + 1) {
      temp[t--] = array[s--];
    }

    for (int i = end, j = end; i >= start; ) {
      array[j--] = temp[i--];
    }
  }
}
